package e_union_find.e_union_find_opt_by_path_compression;

/**
 * 继续优化：在find的同时做路径压缩处理!! 可将并查操作时间复杂度降至接近o(1)水平
 * 这是因为并查集并不限制一个根元素之下孩子元素的个数，最好的优化就是让所有组的rank都不超过1
 *
 * 压缩后每次find都会进行路径压缩处理，提高之后的操作速度
 *
 * path compression 的 两种实现方式
 * 一般情况下方法1就足够好了，方法2并没有带来明显的效率提升
 * 这是因为，方法2压缩的过程中使用了递归，造成了额外的性能消耗
 *
 * 1.find（int id）时
 *      a.如果id不是根元素（父id不等于id），那么将id的pid指向祖父id，接下来查看改变指向后新的id的父元素（原来id的祖父元素）
 *                  5               5               5
 *                 4               4              4    3
 *                3               3                   2  1
 *               2               2  1
 *              1
 * 2. 方式1虽然对路径左了压缩，但是还不是最优情况，最优情况可以压缩到只有一层
 *      a. 使用递归找根节点，然后将遍历的元素的pid全部指向根节点
 *                  5               5
 *                3            1  2  3  4
 *               2
 *              1
 */
public class UnionFind51 {
    private int[] pids; // 为了方便， 索引代表元素id，值代表该位置的元素所指向的pid
    private int[] rank; // rank[i]代表以i为根的组的高度
    private int count; // 并查集包含的元素个数

    /**
     * 传入 size
     * 构造一个以size为大小的并查集，组号从0递增到size-1
     *
     * @param size
     */
    public UnionFind51(int size) {
        this.count = size;
        this.pids = new int[size];
        this.rank = new int[size]; // 组成员人数不包括根，因此高度为0
        for (int i = 0; i < size; i++) {
            this.pids[i] = i;
        }
    }

    /**
     * 查找元素所在组的根id - 接近 O(1）
     *
     * @param p 待查找元素的id
     * @return 带查找元素所在组的根id
     */
    public int find(int p) {
        assert p >= 0 && p < this.count;
        // 向上找到组的根id
        while (p != pids[p]) {
            pids[p] = pids[pids[p]]; // 路径压缩 方法1
            p = pids[p];
        }
        return p;
    }

    /**
     * 判断两个元素id之间是否处于相同的组  - 接近O(1)
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 将p和q所在组联合成一个组  - 接近O(1)
     * 将q所在的组的所有成员都拉入p所在的组中
     * 即让q所在组的根指向p所在组的根即可
     *
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        assert (p >= 0 && p < this.count) && (q >= 0 && q < this.count);

        int pRootID = find(p);
        int qRootID = find(q);

        if (pRootID == qRootID) return;
        if (rank[pRootID] < rank[qRootID]) { // q组高
            pids[pRootID] = qRootID; // 合并到q组
        } else if (rank[pRootID] > rank[qRootID]) { // p组高
            pids[qRootID] = pRootID; // 合并到p组
        }else { // 一样高则统一合并到q组
            pids[qRootID] = pRootID; // 合并到p组
            rank[pRootID] += 1; // 高度加1
        }
    }

    /**
     * 将所有元素都归入第一个元素的组中 - O(n)
     *
     * @param oids
     */
    public void unionAll(int... oids) {
        assert oids != null && oids.length > 1;
        int len = oids.length;
        for (int i = 1; i < len; i++) {
            union(oids[i-1],oids[i]);
        }
    }

    // TODO test method .. to be deleted
    public void testPrint() {
        System.out.print("id  -> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + i);
        }
        System.out.println();
        System.out.print("tid -> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + find(pids[i]));
        }
        System.out.println();
        System.out.print("rank-> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + rank[i]);
        }
        System.out.println("\n=======================");
    }

}
